package dd.prog2.exercises.set05;

/**
 * liste mit locations in TSP
 */
public abstract class Tsp {

	private Place[] tsp;
	private int length;

	public Tsp(int i) {
		this.tsp = new Place[i];// Places als Place[]
		this.length = i;
	}

	public abstract void asGraph();

	@Override
	public String toString() {
		String res = "";
		for (int i = 0; i < tsp.length; i++) {
			res += tsp[i].name + ": " + tsp[i].x + " " + tsp[i].y + "\n";
			System.out.println(tsp[i].name + ": " + tsp[i].x + " " + tsp[i].y);
		}
		return res;
	}
	/*
	 * Ort zu TSP hinzufuegen x, y - Koordinaten, i - index in tsp[]
	 */
	public void addPlace(String name, int i, double x, double y) {
		tsp[i] = new Place(name, x, y);
	}

	/*
	 * berechnet Abstand zw. zwei "Places" in TSP
	 */
	public double calcDistance(int i, int j) {
		// System.out.println("Distance: " + tsp[i].name + "->" + tsp[j].name);
		return (Math.sqrt((tsp[i].x - tsp[j].x) * (tsp[i].x - tsp[j].x)
				+ (tsp[i].y - tsp[j].y) * (tsp[i].y - tsp[j].y)));
	}

	/*
	 * markiert ein Place in TSP als besucht
	 */
	public void setVisited(int i) {
		tsp[i].visited = true;
	}

	/*
	 * prueft ob bereits besucht
	 */
	public boolean isVisited(int i) {
		return tsp[i].visited;
	}

	/*
	 * gibt true zurueck, solange es nicht besuchte Punkte in TSP gibt
	 */
	public boolean hasMoreUnvisited() {
		for (int i = 0; i < tsp.length; i++)
			if (!this.isVisited(i))
				return true;
		return false;
	}

	public int length() {
		return this.length;
	}

	public Place getPlace(int i) {
		return tsp[i];
	}

	/*
	 * berechnet TSP
	 */
	public void calcTSP(Tsp tsp, Trip trip) {
		int minIndex = 0; // Start-Punkt/next-neighbor index
		int currentPlace = 0; // aktueller punkt A
		tsp.setVisited(currentPlace); // wird als besucht markiert
		trip.addPlace(tsp.getPlace(minIndex)); // und als erster zur Loesung hinzugefuegt
		while (tsp.hasMoreUnvisited()) {
			double minDistance = Double.MAX_VALUE; // min-abstand zum next-neighbor, bei jedem durchlauf zuruecksetzen
			for (int i = 0; i < tsp.length(); i++) { // noch nicht besuchte punkte
				if (!tsp.isVisited(i)) {
					double dist = tsp.calcDistance(currentPlace, i); // abstand berechnen
					if (dist < minDistance) {
						minDistance = dist; // min setzen
						minIndex = i; // index von min speichern
					}
				}
			}
			trip.routeLength(minDistance);
			currentPlace = minIndex; // next Punkt hat min Abstand von aktuellem Punkt
			tsp.setVisited(currentPlace); // aktuellen Punkt "besucht" markieren
			trip.addPlace(tsp.getPlace(minIndex));// und zu Trip hinzufuegen
		}
	}
}
